package arithmetic.LeetCode.Degree_of_an_Array;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangyanqi
 * @since 1.0 2017/10/16
 */

@Deprecated
//这个解决方案在快排的时候就内存溢出了
public class Solution {

    public int findShortestSubArray(int[] nums) {
        sort(nums, 0, nums.length - 1);
        List<NumAndCount> list = new LinkedList<>();
        int count = 0;
        int current = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (current == nums[i]) {
                count++;
                if (i == nums.length - 1) {
                    NumAndCount numAndCount = new NumAndCount();
                    numAndCount.setNum(current);
                    numAndCount.setCount(count);
                    list.add(numAndCount);
                }
            } else {
                NumAndCount numAndCount = new NumAndCount();
                numAndCount.setNum(current);
                numAndCount.setCount(count);
                list.add(numAndCount);
                current = nums[i];
                count = 1;
            }
        }
        list.sort((a, b) -> {
            if (a.getCount() > b.getCount()) {
                return -1;
            }
            if (a.getCount() == b.getCount()) {
                return 0;
            }
            if (a.getCount() < b.getCount()) {
                return 1;
            }
            return 0;
        });
        List<Integer> result = new ArrayList<>();
        Iterator<NumAndCount> iterator = list.iterator();
        int first = list.get(0).getCount();
        while (iterator.hasNext()) {
            NumAndCount numAndCount = iterator.next();
            if (numAndCount.getCount() != first) {
                break;
            }
            int begin = 0;
            int end = 0;
            int num = numAndCount.getNum();
            for (int m = 0; m < nums.length; m++) {
                if (nums[m] == num) {
                    begin = m;
                    break;
                }
            }
            for (int b = nums.length - 1; b >= 0; b--) {
                if (nums[b] == num) {
                    end = b;
                    break;
                }
            }
            result.add(end - begin +1);
        }
        result.sort((a, b) -> {
            if (a > b) {
                return 1;
            }
            if (a < b) {
                return -1;
            }
            if (a == b) {
                return 0;
            }
            return 0;
        });
        Integer integer = result.get(0);
        return integer;
    }

    public static void sort(int[] nums, int beginIndex, int endIndex) {
        int position = getPosition(nums, beginIndex, endIndex);
        if (position - 1 > beginIndex) {
            sort(nums, beginIndex, position - 1);
        }
        if (position + 1 < endIndex) {
            sort(nums, position + 1, endIndex);
        }

    }

    public static int getPosition(int[] nums, int beginIndex, int endIndex) {
        int storeIndex = beginIndex;
        int pivot = nums[endIndex];
        for (int i = beginIndex; i <= endIndex; i++) {
            int store = nums[storeIndex];
            //判断sortIndex对应的值是否小于pivot
            while (store <= pivot && storeIndex < endIndex) {
                storeIndex++;
                store = nums[storeIndex];
                if (i < storeIndex) {
                    i = storeIndex;
                }
            }
            //判断边界
            if (storeIndex == endIndex) {
                return storeIndex;
            }
            int num = nums[i];
            if (i == endIndex) {
                nums[storeIndex] = num;
                nums[i] = store;
                return storeIndex;
            }
            if (num <= pivot) {
                nums[storeIndex] = num;
                nums[i] = store;
                storeIndex++;
            }
        }
        return storeIndex;
    }

    private static class NumAndCount {
        public int getNum() {
            return num;
        }

        public void setNum(int num) {
            this.num = num;
        }

        private int num;
        private int count;

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
        }
    }

}

class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] i = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1
                ,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                ,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,
                1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                ,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                ,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,
                1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                ,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
        int shortestSubArray = solution.findShortestSubArray(i);
        System.out.println(shortestSubArray);
    }
}